package com.lw.leetcode.sort.b;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * sort
 * 1642. 可以到达的最远建筑
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/18 9:45
 */
public class FurthestBuilding {


    public static void main(String[] args) {
        FurthestBuilding test = new FurthestBuilding();
        // [14,3,19,3]
        //17
        //0
        int[] arr = {14, 3, 19, 3};
        int a = 17;
        int b = 0;

        int i = test.furthestBuilding(arr, a, b);
        System.out.println(i);
    }


    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        int length = heights.length;
        PriorityQueue<Integer> queue = new PriorityQueue<>(ladders + 1);
        int last = heights[0];
        int sum = 0;
        for (int i = 1; i < length; i++) {
            int v = heights[i];
            if (v > last) {
                queue.add(v - last);
                if (queue.size() > ladders) {
                    sum += queue.poll();
                    if (sum > bricks) {
                        return i - 1;
                    }
                }
            }
            last = v;
        }
        return length - 1;
    }

}
